//给定一个字符串 s ，请将 s 分割成一些子串，使每个子串都是 回文串 ，返回 s 所有可能的分割方案。
//
//
// 回文串 是正着读和反着读都一样的字符串。
//
//
//
// 示例 1：
//
//
//输入：s = "google"
//输出：[["g","o","o","g","l","e"],["g","oo","g","l","e"],["goog","l","e"]]
//
//
// 示例 2：
//
//
//输入：s = "aab"
//输出：[["a","a","b"],["aa","b"]]
//
//
// 示例 3：
//
//
//输入：s = "a"
//输出：[["a"]]
//
//
//
// 提示：
//
//
// 1 <= s.length <= 16
// s 仅由小写英文字母组成
//
//
//
//
//
// 注意：本题与主站 131 题相同： https://leetcode-cn.com/problems/palindrome-partitioning/
//
// Related Topics 深度优先搜索 广度优先搜索 图 哈希表 👍 58 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
function partition(s: string): string[][] {

    function backtracking(startIndex,temp,len) {
        if (len === s.length) {
            res.push(temp.slice())
            return
        }
        for (let i = startIndex; i < s.length; i++) {
            if (!isHuiWen(s.substring(startIndex,i + 1))) continue
            temp.push(s.substring(startIndex,i + 1))
            len += i + 1 - startIndex
            backtracking(i + 1, temp,len)
            temp.pop()
            len -= i + 1 - startIndex
        }
    }
    function isHuiWen(s) {
        let left = 0;
        let right = s.length - 1
        while (left < right) {
            if (s[left] !== s[right]) {
                return false
            }
            left++
            right--
        }
        return true
    }
    let res: string[][] = []
    backtracking(0,[],0)
    return res

};
//leetcode submit region end(Prohibit modification and deletion)
